/*
get the maxinest subsequence
the subsequence is continuous.
*/
#include <stdio.h>

struct subsequence
{
	int sum;
	int start;
	int end;
};

const int FAILURE = -1;
const int SUCCESS = 0;
/*
get the longest positive sequence.
positive sequence means
*/
subsequence getMinsubpositivesequence(int*s, int len)
{
	subsequence Minsubpositivesequence;
	int this_sum = 0;
	if ( len <= 0 )
	{
		Minsubpositivesequence.start = -2;
		return Minsubpositivesequence;
	}
	Minsubpositivesequence.sum = s[0];
	Minsubpositivesequence.start = -1;
	Minsubpositivesequence.end = -1;

	this_sum = 0;
	for(int i = 0 ; i < len; i++)
	{
		this_sum += s[i];
		if(this_sum > 0)
		{
			if(Minsubpositivesequence.sum < 0)
			{
				Minsubpositivesequence.sum = this_sum;
				Minsubpositivesequence.start = i;
				Minsubpositivesequence.end = i;
			}

			if(this_sum < Minsubpositivesequence.sum)
			{
				Minsubpositivesequence.sum = this_sum;
				Minsubpositivesequence.end = i;
			}
		}
	}

	return Minsubpositivesequence;
}



subsequence getMaxsubsequence(int* s, int len)
{
	subsequence maxsubsequence;

	if ( len <= 0 )
	{
		maxsubsequence.start = -1;
		return maxsubsequence;
	}
		
	maxsubsequence.sum = s[0];
	maxsubsequence.start = 0;
	maxsubsequence.end = 0;

	/*int this_sum = s[0];
	
	if (this_sum > 0){
		maxsubsequence.sum = this_sum;
		maxsubsequence.start = 0;
		maxsubsequence.end = 1;
	}
	else{
		maxsubsequence.sum = 0;
		maxsubsequence.start = 0;
		maxsubsequence.end = 0;
	}
	
	for (int i = 1; i < len; ++i)
	{
		this_sum = s[i] > this_sum + s[i] ? s[i] : this_sum + s[i] ;
		//this_sum += s[i];
		if (this_sum >= maxsubsequence.sum)
		{
			maxsubsequence.sum = this_sum;
			maxsubsequence.start = 0;
			maxsubsequence.end = i;
		}
	}*/

	int this_sum = 0;
	int this_sum_start = 0;	
	for (int i = 0; i < len; ++i)
	{
		//this_sum = s[i] > this_sum + s[i] ? s[i] : this_sum + s[i] ;
		this_sum += s[i];
		if (this_sum >= maxsubsequence.sum)
		{
			maxsubsequence.sum = this_sum;
			maxsubsequence.start = this_sum_start;
			maxsubsequence.end = i;
		}
		if (this_sum < 0){
			this_sum = 0;
			this_sum_start = i + 1;
			//this is because that the sum of longestsubsequence is positive, so its contain sum should be positive
			// if this_sum + s[i] is smaller then s[i] this means this_sum is negtive. so its useless to promote the sum.
		}
	}
	return maxsubsequence;
}
int main()
{
	int b[] = {-3,4,5,-4,9,-8};
	int count = 6;
	subsequence maxsubsequence, Minsubpositivesequence;
	maxsubsequence = getMaxsubsequence(b, count);
	if (maxsubsequence.start == -1)
	{
		printf("%s\n", "failed to get Maxsubsequence failed");
	}
	else
	{
		printf("%d\n", maxsubsequence.sum);
		printf("%d\n", maxsubsequence.end);
		printf("%d\n", maxsubsequence.start);
	}

	/*Minsubpositivesequence = getMinsubpositivesequence(b, count);
	if(Minsubpositivesequence.start == -2)
	{
		printf("%s\n", "Failed to get subsequence");
	}
	else if(Minsubpositivesequence.start == -1)
	{
		printf("%s\n", "no subsequence exists");
	}
	else
	{
		printf("%d\n", Minsubpositivesequence.sum);
	}*/
	
}